package 高频题;

import java.util.Stack;

public class 每日温度_739 {
    public int[] dailyTemperatures(int[] T) {
        int[] result = new int[T.length];


        Stack<Integer> stack = new Stack<>();
        for (int i = T.length - 1; i >= 0; i--) {
            // 如果栈不为空且当前温度大于栈顶温度
            // 由于是逆序遍历，所以栈中索引对应的温度不可能比其之前某天温度高
            // 所以将栈中存取的温度出栈，直到栈为空或当前温度小于栈顶索引对应温度
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
                stack.pop();
            }
            // 1.如果栈不为空，且当前温度小于栈顶温度，由于是逆序遍历
            // 所以栈顶温度是比当前温度高的一天，
            // 栈顶温度对应的索引减去当前温度的索引就是差的天数
            // 2.如果栈为空，说明当前温度之后没有比其高的温度，根据题意值为0
            result[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);//注意  栈中存放的是下标
        }
        return result;
    }
}
